1. Field of the Invention
The present invention generally relates to a hardware implementation of sort and merge operations in a data processing system and, more particularly, to high performance sort hardware for a database accelerator. In a specific application, the invention is directed to electronic circuitry which implements the Van Voorhis n=16 sort network.
2. Description of the Prior Art
In database operations, the sort operation takes a list of elements, such as Tom, Dick, Harry, and Francois, and rearranges them in ascending or descending order based on alphabetic or numeric value of each character as, for example, Tom, Harry, Francois, and Dick.
Donald E. Knuth in The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., (1973), describes sort networks as a collection of comparators. As illustrated in FIG. 1, each comparator 11, 12, 13, 14, and 15 has two inputs and two outputs. The input comparator 11 receives the elements Tom and Dick, in this example, while the input comparator 12 receives the elements Harry and Francois. These comparators order the input elements according to a prescribed order such that, in this case, the Tom and Dick elements are, respectively, high (H) and low (L) order outputs of input comparator 11, and the Harry and Francois elements are, respectively, H and L order outputs of input comparator 12. The H order outputs of input comparators 11 and 12 are connected to the inputs of comparator 13, and the L order outputs of the input comparators 11 and 12 are connected to the inputs of comparator 14. Again, these comparators order their respective input elements according to a prescribed order such that, in this case, the Tom and Harry elements are, respectively, the H and L outputs of comparator 13 and the Francois and Dick elements are, respectively, the H and L outputs of comparator 14. The L output from comparator 13 and the H output of comparator 14 are connected to the inputs of comparator 15, which outputs the Harry element as its H output and the Francois elements as its L output, thereby providing the ordering Tom, Harry, Francois, and Dick.
Sort networks are conventionally represented by graphs of the type shown in FIG. 2 where data flows left to right, vertical lines represent comparators, and dots show comparator input and output. The graph shown in FIG. 2 represents the sort network of FIG. 1. See Knuth, supra, "Networks for Sorting", pp. 220-235. Knuth states that the best sorting networks currently known were constructed by D. Van Voorhis in 1974. His networks require 1/4n(lg n).sup.2 -.alpha.n lg n+O(n) comparators, where n is the number of elements to be sorted and .alpha..apprxeq.0.395367. FIG. 3 is a graph similar to FIG. 2 for the Van Voorhis n=16 network. This network sorts a list of sixteen elements using sixty-one comparator modules. This network has a "delay" of nine because the longest path goes through nine comparators.
Clearly, there is a problem in implementing the Van Voorhis algorithm since sixty-one comparator modules are required. Current thermal conduction modules (TCMs) may contain up to 121 integrated circuit (IC) chip sites. In IBM System/370 architecture using a 32-bit word, comparators would need to be able to operate on two quadwords (QWs). Thus, if one comparator were implemented in a single chip, then that chip would have two QW inputs and two QW outputs, i.e., 128 bits each plus sixteen error checking and correcting (ECC) bits. Each chip would therefore require at least 576 pins, and 288 pins on each of the chips would switch simultaneously. This would not be a viable TCM design.